package previous.Test_0219;

import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
 class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
public class Solution {
     //重排链表
    public void reorderList(ListNode head) {
        //如果head为空或者只有一个或者两个节点
        if(head==null || head.next==null || head.next.next==null){
            return;
        }
        ListNode fast=head,slow=head;
          //快慢双指针：寻找中间点
        while(fast!=null &&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        //翻转链表
        //从slow下一个节点开始反转
        ListNode h=new ListNode(0);
        ListNode cur=slow.next;
        //将两个链表分离
        slow.next=null;
        while(cur!=null){
            //n记录下一个节点
            ListNode n=cur.next;
            //将cur指向h
            cur.next=h.next;
            h.next=cur;
            //cur到原来的下一个节点
            cur=n;
        }
        //合并两个链表
        ListNode cur1=head;
        ListNode cur2=h.next;
        ListNode prev=new ListNode(0);
        while(cur1!=null){
            prev.next=cur1;
            prev=cur1;
            cur1=cur1.next;
            if(cur2!=null){
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
    }
    //合并k个升序链表
    //优先级队列：超时
    public ListNode mergeKLists1(ListNode[] lists) {
        //创建一个小根堆
        PriorityQueue<ListNode> heap=new PriorityQueue<>((v1,v2)->v1.val-v2.val);
        //把所有头结点放到堆里面
        for(ListNode head:heap){
            if(head!=null){
                heap.offer(head);
            }
        }
        //合并链表
        ListNode ret=new ListNode(0);
        ListNode prev=ret;
        while(!heap.isEmpty()){
            ListNode t=heap.poll();
            prev.next=t;
            prev=t;
            if(t.next!=null){
                heap.offer(t.next);
            }
        }
        return ret.next;
    }
    //归并方法
    public ListNode mergeKLists(ListNode[] lists) {
          return  merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int l,int r){
        if(l>r){
            return null;
        }
        if(l==r){
            return lists[l];
        }
        //平分
        int mid=(l+r)/2;
        //递归左右
       ListNode l1= merge(lists,l,mid);
       ListNode l2= merge(lists,mid+1,r);
        //合并
        return mergeTwolist(l1,l2);
    }
    public ListNode mergeTwolist(ListNode l1,ListNode l2){
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        //合并
        ListNode cur1=l1;
        ListNode cur2=l2;
        ListNode ret=new ListNode(0);
        ListNode prev=ret;
        while(cur1!=null && cur2!=null ){
            if(cur1.val<cur2.val){
            prev.next=cur1;
            prev=cur1;
            cur1=cur1.next;
            } else{
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
        if(cur1!=null) prev.next=cur1;
        if(cur2!=null) prev.next=cur2;
        return ret.next;
    }
    //k个一组翻转链表
    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode p=head;
        int n=0;
        int count=0;
         //求出多少个需要逆序
        while(p!=null){
            p=p.next;
            count++;
        }
        n=count/k;
        ListNode ret=new ListNode(0);
        ListNode prev=ret;
        ListNode cur=head;
        //重复n次逆转
        while(n!=0){
            int j=k;
            ListNode tmp=cur;
            while(j!=0){
                ListNode next=cur.next;
                cur.next=prev.next;
                prev.next=cur;
                cur=next;
                j--;
            }
            prev=tmp;
            n--;
        }
        prev.next=cur;
        return ret.next;
    }
    //两数之和
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> hash=new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int x=nums[i]-target;
            if(hash.containsKey(x)){
                return new int[]{i,hash.get(x)};
            }
            hash.put(nums[i],i);
        }
        return new int[]{-1,-1};
    }
}
